#ifndef	_SYS_QUEUE_H_
#define	_SYS_QUEUE_H_
/*
 * This file defines five types of data structures: singly-linked lists,
 * lists, simple queues, tail queues, and circular queues.
 *
 * A singly-linked list is headed by a single forward pointer. The
 * elements are singly linked for minimum space and pointer manipulation
 * overhead at the expense of O(n) removal for arbitrary elements. New
 * elements can be added to the list after an existing element or at the
 * head of the list.  Elements being removed from the head of the list
 * should use the explicit macro for this purpose for optimum
 * efficiency. A singly-linked list may only be traversed in the forward
 * direction.  Singly-linked lists are ideal for applications with large
 * datasets and few or no removals or for implementing a LIFO queue.
 *
 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.
 *
 * A simple queue is headed by a pair of pointers, one the head of the
 * list and the other to the tail of the list. The elements are singly
 * linked to save space, so elements can only be removed from the
 * head of the list. New elements can be added to the list after
 * an existing element, at the head of the list, or at the end of the
 * list. A simple queue may only be traversed in the forward direction.
 *
 * A tail queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or
 * after an existing element, at the head of the list, or at the end of
 * the list. A tail queue may be traversed in either direction.
 *
 * A circle queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or after
 * an existing element, at the head of the list, or at the end of the list.
 * A circle queue may be traversed in either direction, but has a more
 * complex end of list detection.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */

/*
 * List definitions.
 */
#define	LIST_HEAD(name,type)						                 \
struct name {								                         \
	struct type *lh_first;	/* first element */		      	         \
}

#define	LIST_HEAD_INITIALIZER(head)					                 \
	{NULL}

#define	LIST_ENTRY(type)						                     \
struct {								                             \
	struct type *le_next;	/* next element */			             \
	struct type **le_prev;	/* address of previous next element */	 \
}
/*
 * List functions.
 */
#define	LIST_INIT(head) do {					                     \
	(head)->lh_first=NULL;					                         \
} while (0)

#define	LIST_INSERT_AFTER(listelm,elm,field) do {			         \
	if (((elm)->field.le_next=(listelm)->field.le_next)!=NULL)	     \
		(listelm)->field.le_next->field.le_prev=		             \
		    &(elm)->field.le_next;				                     \
	(listelm)->field.le_next=(elm);				                     \
	(elm)->field.le_prev=&(listelm)->field.le_next;		             \
} while (0)

#define	LIST_INSERT_BEFORE(listelm,elm,field) do {			         \
	(elm)->field.le_prev=(listelm)->field.le_prev;		             \
	(elm)->field.le_next=(listelm);				                     \
	*(listelm)->field.le_prev=(elm);				                 \
	(listelm)->field.le_prev =&(elm)->field.le_next;		         \
} while (0)

#define	LIST_INSERT_HEAD(head,elm,field) do {				         \
	if (((elm)->field.le_next=(head)->lh_first)!=NULL)		         \
		(head)->lh_first->field.le_prev=&(elm)->field.le_next;       \
	(head)->lh_first=(elm);					                         \
	(elm)->field.le_prev=&(head)->lh_first;			                 \
} while (0)

#define	LIST_REMOVE(elm,field) do {					                 \
	if ((elm)->field.le_next!=NULL)				                     \
		(elm)->field.le_next->field.le_prev= 			             \
		    (elm)->field.le_prev;			 	                     \
	*(elm)->field.le_prev=(elm)->field.le_next;			             \
} while (0)

#define	LIST_FOREACH(var,head,field)				 	             \
	for ((var)=((head)->lh_first);				                     \
		(var);							                             \
		(var)=((var)->field.le_next))

/*
 * List access methods.
 */
#define	LIST_EMPTY(head)		((head)->lh_first==NULL)
#define	LIST_FIRST(head)		((head)->lh_first)
#define	LIST_NEXT(elm,field)    ((elm)->field.le_next)

/*
 * Singly-linked List definitions.
 */
#define	SLIST_HEAD(name,type)						                 \
struct name {								                         \
	struct type *slh_first;	/* first element */			             \
}

#define	SLIST_HEAD_INITIALIZER(head)					             \
	{NULL}

#define	SLIST_ENTRY(type)						                     \
struct {								                             \
	struct type *sle_next;	/* next element */			             \
}

/*
 * Singly-linked List functions.
 */
#define	SLIST_INIT(head) do {						                 \
	(head)->slh_first=NULL;					                         \
} while (0)

#define	SLIST_INSERT_AFTER(slistelm,elm,field) do {			         \
	(elm)->field.sle_next=(slistelm)->field.sle_next;		         \
	(slistelm)->field.sle_next=(elm);				                 \
} while (0)

#define	SLIST_INSERT_HEAD(head,elm,field) do {			             \
	(elm)->field.sle_next=(head)->slh_first;			             \
	(head)->slh_first=(elm);					                     \
} while (0)

#define	SLIST_REMOVE_HEAD(head,field) do {				             \
	(head)->slh_first=(head)->slh_first->field.sle_next;		     \
} while (0)

#define	SLIST_REMOVE(head,elm,type,field) do {			             \
	if ((head)->slh_first==(elm)) {				                     \
		SLIST_REMOVE_HEAD((head),field);			                 \
	}								                                 \
	else {								                             \
		struct type *curelm=(head)->slh_first;	   	                 \
		while(curelm->field.sle_next!=(elm))			             \
			curelm=curelm->field.sle_next;		                     \
		curelm->field.sle_next=				                         \
		    curelm->field.sle_next->field.sle_next;		             \
	}								                                 \
} while (0)

#define	SLIST_FOREACH(var,head,field)					             \
	for ((var)=(head)->slh_first;(var);(var)=(var)->field.sle_next)

/*
 * Singly-linked List access methods.
 */
#define	SLIST_EMPTY(head)	((head)->slh_first==NULL)
#define	SLIST_FIRST(head)	((head)->slh_first)
#define	SLIST_NEXT(elm,field)	((elm)->field.sle_next)

/*
 * Singly-linked Tail queue declarations.
 */
#define	STAILQ_HEAD(name,type)					                     \
struct name {								                         \
	struct type *stqh_first;	/* first element */			         \
	struct type **stqh_last;	/* addr of last next element */		 \
}

#define	STAILQ_HEAD_INITIALIZER(head)					             \
	{NULL,&(head).stqh_first}

#define	STAILQ_ENTRY(type)						                     \
struct {								                             \
	struct type *stqe_next;	/* next element */			             \
}

/*
 * Singly-linked Tail queue functions.
 */
#define	STAILQ_INIT(head) do {						                 \
	(head)->stqh_first=NULL;					                     \
	(head)->stqh_last =&(head)->stqh_first;				             \
} while (0)

#define	STAILQ_INSERT_HEAD(head,elm,field) do {			             \
	if (((elm)->field.stqe_next=(head)->stqh_first)==NULL)	         \
		(head)->stqh_last=&(elm)->field.stqe_next;		             \
	(head)->stqh_first=(elm);					                     \
} while (0)

#define	STAILQ_INSERT_TAIL(head,elm,field) do {			             \
	(elm)->field.stqe_next=NULL;					                 \
	*(head)->stqh_last=(elm);					                     \
	(head)->stqh_last =&(elm)->field.stqe_next;			             \
} while (0)

#define	STAILQ_INSERT_AFTER(head,listelm,elm,field) do {		     \
	if (((elm)->field.stqe_next=(listelm)->field.stqe_next)==NULL)   \
		(head)->stqh_last=&(elm)->field.stqe_next;		             \
	(listelm)->field.stqe_next=(elm);				                 \
} while (0)

#define	STAILQ_REMOVE_HEAD(head,field) do {				             \
	if (((head)->stqh_first=(head)->stqh_first->field.stqe_next)==NULL) \
		(head)->stqh_last=&(head)->stqh_first;			             \
} while (0)

#define	STAILQ_REMOVE(head,elm,type,field) do {			             \
	if ((head)->stqh_first==(elm)) {				                 \
		STAILQ_REMOVE_HEAD((head),field);			                 \
	} else {							                             \
		struct type *curelm=(head)->stqh_first;		                 \
		while (curelm->field.stqe_next!=(elm))			             \
			curelm=curelm->field.stqe_next;		                     \
		if ((curelm->field.stqe_next=				                 \
			curelm->field.stqe_next->field.stqe_next)==NULL)         \
			    (head)->stqh_last=&(curelm)->field.stqe_next;        \
	}								                                 \
} while (0)

#define	STAILQ_FOREACH(var,head,field)				                 \
	for ((var)=((head)->stqh_first);				                 \
		(var);							                             \
		(var)=((var)->field.stqe_next))

#define	STAILQ_CONCAT(head1,head2) do {				                 \
	if (!STAILQ_EMPTY((head2))) {					                 \
		*(head1)->stqh_last=(head2)->stqh_first;		             \
		(head1)->stqh_last =(head2)->stqh_last;		                 \
		STAILQ_INIT((head2));					                     \
	}								                                 \
} while (0)

/*
 * Singly-linked Tail queue access methods.
 */
#define	STAILQ_EMPTY(head)	((head)->stqh_first==NULL)
#define	STAILQ_FIRST(head)	((head)->stqh_first)
#define	STAILQ_NEXT(elm,field)	((elm)->field.stqe_next)


/*
 * Simple queue definitions.
 */
#define	SIMPLEQ_HEAD(name,type)					                     \
struct name {								                         \
	struct type *sqh_first;	/* first element */			             \
	struct type **sqh_last;	/* addr of last next element */		     \
}

#define	SIMPLEQ_HEAD_INITIALIZER(head)					             \
	{NULL,&(head).sqh_first}

#define	SIMPLEQ_ENTRY(type)						                     \
struct {								                             \
	struct type *sqe_next;	/* next element */			             \
}

/*
 * Simple queue functions.
 */
#define	SIMPLEQ_INIT(head) do {						                 \
	(head)->sqh_first=NULL;					                         \
	(head)->sqh_last=&(head)->sqh_first;				             \
} while (0)

#define	SIMPLEQ_INSERT_HEAD(head,elm,field) do {			         \
	if (((elm)->field.sqe_next=(head)->sqh_first)==NULL)	         \
		(head)->sqh_last=&(elm)->field.sqe_next;		             \
	(head)->sqh_first=(elm);					                     \
} while (0)

#define	SIMPLEQ_INSERT_TAIL(head,elm,field) do {			         \
	(elm)->field.sqe_next=NULL;					                     \
	*(head)->sqh_last=(elm);					                     \
	(head)->sqh_last=&(elm)->field.sqe_next;			             \
} while (0)

#define	SIMPLEQ_INSERT_AFTER(head,listelm,elm,field) do {		     \
	if (((elm)->field.sqe_next=(listelm)->field.sqe_next)==NULL)     \
		(head)->sqh_last=&(elm)->field.sqe_next;		             \
	(listelm)->field.sqe_next=(elm);			  	                 \
} while (0)

#define	SIMPLEQ_REMOVE_HEAD(head,field) do {				         \
	if (((head)->sqh_first=(head)->sqh_first->field.sqe_next)==NULL) \
		(head)->sqh_last=&(head)->sqh_first;			             \
} while (0)

#define	SIMPLEQ_REMOVE(head,elm,type,field) do {			         \
	if ((head)->sqh_first==(elm)) {				                     \
		SIMPLEQ_REMOVE_HEAD((head),field);			                 \
	} else {							                             \
		struct type *curelm=(head)->sqh_first;		                 \
		while (curelm->field.sqe_next!=(elm))			             \
			curelm=curelm->field.sqe_next;		                     \
		if ((curelm->field.sqe_next=				                 \
			curelm->field.sqe_next->field.sqe_next)==NULL)           \
			    (head)->sqh_last=&(curelm)->field.sqe_next;          \
	}								                                 \
} while (0)

#define	SIMPLEQ_FOREACH(var,head,field)				                 \
	for ((var)=((head)->sqh_first);				                     \
		(var);							                             \
		(var)=((var)->field.sqe_next))

/*
 * Simple queue access methods.
 */
#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first==NULL)
#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
#define	SIMPLEQ_NEXT(elm,field)	((elm)->field.sqe_next)

/*
 * Tail queue definitions.
 */
#define	_TAILQ_HEAD(name,type,qual)					                 \
struct name {								                         \
	qual type *tqh_first;		/* first element */		             \
	qual type *qual *tqh_last;	/* addr of last next element */	     \
}
#define TAILQ_HEAD(name,type)	_TAILQ_HEAD(name,struct type,)

#define	TAILQ_HEAD_INITIALIZER(head)					             \
	{NULL,&(head).tqh_first }

#define	_TAILQ_ENTRY(type,qual)					                     \
struct {								                             \
	qual type *tqe_next;		/* next element */		             \
	qual type *qual *tqe_prev;	/* address of previous next element */\
}
#define TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type,)

/*
 * Tail queue functions.
 */
#define	TAILQ_INIT(head) do {						                 \
	(head)->tqh_first=NULL;					                         \
	(head)->tqh_last=&(head)->tqh_first;				             \
} while (0)

#define	TAILQ_INSERT_HEAD(head,elm,field) do {			             \
	if (((elm)->field.tqe_next=(head)->tqh_first)!=NULL)	         \
		(head)->tqh_first->field.tqe_prev=			                 \
		    &(elm)->field.tqe_next;				                     \
	else								                             \
		(head)->tqh_last=&(elm)->field.tqe_next;		             \
	(head)->tqh_first=(elm);					                     \
	(elm)->field.tqe_prev=&(head)->tqh_first;			             \
} while (0)

#define	TAILQ_INSERT_TAIL(head,elm,field) do {			             \
	(elm)->field.tqe_next=NULL;					                     \
	(elm)->field.tqe_prev=(head)->tqh_last;			                 \
	*(head)->tqh_last=(elm);					                     \
	(head)->tqh_last =&(elm)->field.tqe_next;			             \
} while (0)

#define	TAILQ_INSERT_AFTER(head,listelm,elm,field) do {		         \
	if (((elm)->field.tqe_next=(listelm)->field.tqe_next)!=NULL)     \
		(elm)->field.tqe_next->field.tqe_prev=        		         \
		    &(elm)->field.tqe_next;				                     \
	else								                             \
		(head)->tqh_last=&(elm)->field.tqe_next;		             \
	(listelm)->field.tqe_next=(elm);				                 \
	(elm)->field.tqe_prev=&(listelm)->field.tqe_next;		         \
} while (0)

#define	TAILQ_INSERT_BEFORE(listelm,elm,field) do {			         \
	(elm)->field.tqe_prev=(listelm)->field.tqe_prev;		         \
	(elm)->field.tqe_next=(listelm);				                 \
	*(listelm)->field.tqe_prev=(elm);				                 \
	(listelm)->field.tqe_prev =&(elm)->field.tqe_next;		         \
} while (0)

#define	TAILQ_REMOVE(head,elm,field) do {				             \
	if (((elm)->field.tqe_next)!=NULL)				                 \
		(elm)->field.tqe_next->field.tqe_prev= 	        	         \
		    (elm)->field.tqe_prev;				                     \
	else								                             \
		(head)->tqh_last=(elm)->field.tqe_prev;		                 \
	*(elm)->field.tqe_prev=(elm)->field.tqe_next;			         \
} while (0)

#define	TAILQ_FOREACH(var,head,field)					             \
	for ((var)=((head)->tqh_first);				                     \
		(var);							                             \
		(var)=((var)->field.tqe_next))

#define	TAILQ_FOREACH_REVERSE(var,head,headname,field)		         \
	for ((var)=(*(((struct headname *)((head)->tqh_last))->tqh_last));	\
		(var);							                             \
		(var)=(*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))

#define	TAILQ_CONCAT(head1,head2,field) do {				         \
	if (!TAILQ_EMPTY(head2)) {					                     \
		*(head1)->tqh_last=(head2)->tqh_first;		                 \
		(head2)->tqh_first->field.tqe_prev=(head1)->tqh_last;	     \
		(head1)->tqh_last=(head2)->tqh_last;			             \
		TAILQ_INIT((head2));					                     \
	}								                                 \
} while (0)

/*
 * Tail queue access methods.
 */
#define	TAILQ_EMPTY(head)		((head)->tqh_first==NULL)
#define	TAILQ_FIRST(head)		((head)->tqh_first)
#define	TAILQ_NEXT(elm,field)   ((elm)->field.tqe_next)

#define	TAILQ_LAST(head,headname)                                    \
	(*(((struct headname *)((head)->tqh_last))->tqh_last))
#define	TAILQ_PREV(elm,headname,field)                               \
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

/*
 * Circular queue definitions.
 */
#define	CIRCLEQ_HEAD(name,type)					                     \
struct name {								                         \
	struct type *cqh_first;		/* first element */		             \
	struct type *cqh_last;		/* last element */		             \
}

#define	CIRCLEQ_HEAD_INITIALIZER(head)					             \
	{(void *)&head,(void *)&head}

#define	CIRCLEQ_ENTRY(type)						                     \
struct {								                             \
	struct type *cqe_next;		/* next element */		             \
	struct type *cqe_prev;		/* previous element */		         \
}

/*
 * Circular queue functions.
 */
#define	CIRCLEQ_INIT(head) do {						                 \
	(head)->cqh_first=(void *)(head);				                 \
	(head)->cqh_last =(void *)(head);				                 \
} while (0)

#define	CIRCLEQ_INSERT_AFTER(head,listelm,elm,field) do {		     \
	(elm)->field.cqe_next=(listelm)->field.cqe_next;		         \
	(elm)->field.cqe_prev=(listelm);				                 \
	if ((listelm)->field.cqe_next==(void *)(head))		             \
		(head)->cqh_last=(elm);				                         \
	else								                             \
		(listelm)->field.cqe_next->field.cqe_prev=(elm);	         \
	(listelm)->field.cqe_next=(elm);				                 \
} while (0)

#define	CIRCLEQ_INSERT_BEFORE(head,listelm,elm,field) do {		     \
	(elm)->field.cqe_next=(listelm);				                 \
	(elm)->field.cqe_prev=(listelm)->field.cqe_prev;		         \
	if ((listelm)->field.cqe_prev==(void *)(head))		             \
		(head)->cqh_first=(elm);				                     \
	else								                             \
		(listelm)->field.cqe_prev->field.cqe_next=(elm);	         \
	(listelm)->field.cqe_prev=(elm);				                 \
} while (0)

#define	CIRCLEQ_INSERT_HEAD(head,elm,field) do {			         \
	(elm)->field.cqe_next=(head)->cqh_first;			             \
	(elm)->field.cqe_prev=(void *)(head);				             \
	if ((head)->cqh_last==(void *)(head))				             \
		(head)->cqh_last=(elm);				                         \
	else							 	                             \
		(head)->cqh_first->field.cqe_prev=(elm);		             \
	(head)->cqh_first=(elm);					                     \
} while (0)

#define	CIRCLEQ_INSERT_TAIL(head,elm,field) do {			         \
	(elm)->field.cqe_next=(void *)(head);				             \
	(elm)->field.cqe_prev=(head)->cqh_last;		 	                 \
	if ((head)->cqh_first==(void *)(head))			                 \
		(head)->cqh_first=(elm);				                     \
	else								                             \
		(head)->cqh_last->field.cqe_next=(elm);		                 \
	(head)->cqh_last=(elm);					                         \
} while (0)

#define	CIRCLEQ_REMOVE(head,elm,field) do {				             \
	if ((elm)->field.cqe_next==(void *)(head))			             \
		(head)->cqh_last=(elm)->field.cqe_prev;		                 \
	else								                             \
		(elm)->field.cqe_next->field.cqe_prev=			             \
		    (elm)->field.cqe_prev;				                     \
	if ((elm)->field.cqe_prev==(void *)(head))			             \
		(head)->cqh_first=(elm)->field.cqe_next;		             \
	else								                             \
		(elm)->field.cqe_prev->field.cqe_next=			             \
		    (elm)->field.cqe_next;				                     \
} while (0)

#define	CIRCLEQ_FOREACH(var,head,field)				                 \
	for ((var)=((head)->cqh_first);				                     \
		(var)!=(const void *)(head);				                 \
		(var) =((var)->field.cqe_next))

#define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			         \
	for ((var)=((head)->cqh_last);				                     \
		(var)!=(const void *)(head);				                 \
		(var) =((var)->field.cqe_prev))

/*
 * Circular queue access methods.
 */
#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first==(void *)(head))
#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
#define	CIRCLEQ_NEXT(elm,field)	((elm)->field.cqe_next)
#define	CIRCLEQ_PREV(elm,field)	((elm)->field.cqe_prev)

#define CIRCLEQ_LOOP_NEXT(head,elm,field)				             \
	(((elm)->field.cqe_next==(void *)(head))			             \
	    ?((head)->cqh_first)					                     \
	    :(elm->field.cqe_next))
#define CIRCLEQ_LOOP_PREV(head,elm,field)				             \
	(((elm)->field.cqe_prev==(void *)(head))			             \
	    ?((head)->cqh_last)		     			                     \
	    :(elm->field.cqe_prev))

#endif
